﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace StringManipulation
{
    partial class Program
    {
        //prints the first nonrepeated character in a string
        public static char FirstNonRepeatedCharacter(string strVal)
        {
            int strLen = strVal.Length;
            Hashtable strTable = new Hashtable();

            foreach (char c in strVal)
            {
                if (!strTable.ContainsKey(c))
                    strTable.Add(c, 1);
                else
                    strTable[c]= (int)(strTable[c])+1;                   
            }
            
            foreach(char c in strVal)
            {
                if (strTable[c].Equals(1))
                    return c;
            }

            return '0';
        }

        public static void RemoveChar(string str, string removeChar)
        {

        }

        // binary search on a sorted array
        public static int BinarySearchWrapper(int[] sortedArray, int target)
        {
            int upper = sortedArray.Length;
            return BinarySearch(sortedArray, 0, upper, target);
        }

        // binary search on a sorted array
        public static int BinarySearch(int[] sortedArray, int lower, int upper, int target)
        {
            int range = upper - lower;

            if (range < 0)
            {
                return -1;
            }
            else if (range == 0 && sortedArray[lower] != target)
                return -2;

            int middle = range/ 2 + lower;
            if (sortedArray[middle] == target)
                return middle;
            else if (sortedArray[middle] < target)
            {
                return BinarySearch(sortedArray, middle+1, upper, target);
            }
            else
                return BinarySearch(sortedArray, lower, middle-1, target);

        }

        // if string is "Do not try." return "try. not Do"
        public static string ReverseWordsInString(string str)
        {
            Stack charStack = new Stack();
            string newString = "";
            for (int i = str.Length -1 ; i >= 0; i-- )
            {
                if (!char.IsWhiteSpace(str[i]))
                {
                    charStack.Push(str[i]);
                }
                else
                {
                    while (charStack.Count > 0)
                    {
                        newString += charStack.Pop();
                    }
                    newString += ' ';
                }
            }
            while (charStack.Count > 0)
            {
                newString += charStack.Pop();
            }
            return newString;
        }

        // print all the permutation of an array of characters even if they are repeated
        public static void Permute(char[] inArr)
        {
            int length = inArr.Length;
            char[] outArr = new char[length];

            int[] used = new int[length];

            //mark all characters as unused
            for (int i = 0; i < length; i++)
            {
                used[i] = 0;
            }
            int count = 1;
            DoPermute(inArr, ref outArr, ref used, length, 0, ref count);
        }

        public static void DoPermute(char[] inArr, ref char[] outArr, ref int[] used, int length, int recursiveLev, ref int count)
        {

            if (recursiveLev >= length)
            {
                Console.Write(count.ToString() + " ");
                Console.WriteLine(outArr);
                count++;
                return;
            }

            for (int i = 0; i < length; i++)
            {
                if (used[i] == 1)
                {
                    continue;
                }
                outArr[recursiveLev] = inArr[i];
                used[i] = 1;
                DoPermute(inArr, ref outArr, ref used, length, recursiveLev + 1, ref count);
                used[i] = 0;
            }

        }

        //print all the combination of an array of characters '123' = 1,2,3,12,13,123,23
        public static void Combine(char[] inArr)
        {
            int inArrIndex = 0;
            int length = inArr.Length;
            int recursiveLev = 0;
            char[] outArr = new char[length+1];
            DoCombine(inArr, outArr, inArrIndex, recursiveLev, length);
        }

        public static void DoCombine(char[] inArr, char[] outArr, int inArrIndex, int recursiveLev, int length)
        {
            for (int i = inArrIndex; i <= length-1; i++)
            {
                outArr[recursiveLev] = inArr[i];
                outArr[recursiveLev + 1] = '\0';
                Console.WriteLine(outArr);
                if(recursiveLev <= length-1)
                    DoCombine(inArr, outArr, i+1, recursiveLev + 1, length);
            }
        }

        //print all the permutation of words represented by telephone numbers
        public static void PrintTelephoneWords(int[] phoneNum)
        {
            Dictionary<int, char[]> teleDict = new Dictionary<int, char[]>();

            int count = 0;
            for (int i = 2; i < 10; i++)
            {
                char[] arr = new char[3];
                for (int j = 0; j < 3; j++)
                {
                    arr[j] = (char) ('a' + count * 3 + j);
                }
                teleDict.Add(i, arr);
                count++;
            }

            char[] outArr = new char[phoneNum.Length];
            DoPrintTelephoneWords(phoneNum, ref outArr, 0, phoneNum.Length, teleDict);
        }

        public static void DoPrintTelephoneWords(int[] phoneNum, ref char[] outArr, int recursiveLev, int length, Dictionary<int, char[]> teleDict)
        {
            if (recursiveLev == length)
            {
                Console.WriteLine(outArr);
                return;
            }

            if (phoneNum[recursiveLev] == 0)
            {
                outArr[recursiveLev] = '0';
                DoPrintTelephoneWords(phoneNum, ref outArr, recursiveLev + 1, length, teleDict);
            }
            else if (phoneNum[recursiveLev] == 1)
            {
                outArr[recursiveLev] = '1';
                DoPrintTelephoneWords(phoneNum, ref outArr, recursiveLev + 1, length, teleDict);
            }
            else
            {
                char[] arr = new char[3];
                if (teleDict.ContainsKey(phoneNum[recursiveLev]))
                    arr = teleDict[phoneNum[recursiveLev]];
                for (int i = 0; i < 3; i++)
                {
                    outArr[recursiveLev] = arr[i];
                    DoPrintTelephoneWords(phoneNum, ref outArr, recursiveLev + 1, length, teleDict);
                }
            }
        }

        static void Main(string[] args)
        {
            //program to return the first non repeated character
            string strVal = "noononolmlmipapa";
            Console.WriteLine("PROGRAM TO RETURN THE FIRST NON REPEATED CHARACTER");
            Console.WriteLine("____________________________________________________________________________");
            Console.WriteLine("First Non-Repeated character in {0} is {1}", strVal, FirstNonRepeatedCharacter(strVal));
            Console.WriteLine();

            strVal = "Do not try.";
            Console.WriteLine("PROGRAM TO RETURN THE WORDS REVERSED IN A STRING");
            Console.WriteLine("____________________________________________________________________________");
            Console.WriteLine("String is {0} and reversedstring is {1}", strVal, ReverseWordsInString(strVal));
            Console.WriteLine();

            int[] intArray = new int[12] {1,3,5,6,7,9,13,14,17,23,25,30};
            int target = 17;
            Console.WriteLine("PROGRAM TO RETURN THE INDEX OF THE VALUE SEARCHED IN A SORTED ARRAY");
            Console.WriteLine("____________________________________________________________________________");
            Console.WriteLine("Array is {0}, target is {1} and index is {2}", intArray, target.ToString(), BinarySearchWrapper(intArray, target));
            Console.WriteLine();

            char[] inArr = new char[] { 'a', 'x', 'f'};//,'s', 'd', 'm'};
            Console.WriteLine("PROGRAM TO PRINT THE PERMUTATION IN A CHAR ARRAY");
            Console.WriteLine("____________________________________________________________________________");
            Permute(inArr);
            Console.WriteLine();

            Console.WriteLine("APPOINTMENT LIST CONFLICT");
            Console.WriteLine("____________________________________________________________________________");
            List<Appointment> applist = MarkConflicts(CreateAppointmentList());
            foreach (Appointment ap in applist)
            {
                Console.WriteLine("StartTime = {0} EndTime{1} HasConflict = {2}", ap.StartDate.ToString(), ap.EndDate.ToString(), ap.HasConflict.ToString());
            }
            Console.WriteLine();

            char[] inArr1 = new char[] { 'w', 'x', 'y', 'z' };//,'s', 'd', 'm'};
            Console.WriteLine("PROGRAM TO PRINT THE COMBINATION IN A CHAR ARRAY");
            Console.WriteLine("____________________________________________________________________________");
            Combine(inArr1);
            Console.WriteLine();

            int[] inArr2 = new int[] { 2, 6, 9 };//,'s', 'd', 'm'};
            Console.WriteLine("PROGRAM TO PRINT THE PERMUTATION IN A TelePhone NUMBER");
            Console.WriteLine("____________________________________________________________________________");
            PrintTelephoneWords(inArr2);
            Console.WriteLine();

            Console.ReadKey();
        }
    }
}
